home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / muds / lpmud312.tar / lpmud312 / stralloc.c < prev    next >
C/C++ Source or Header  |  1991-10-31  |  7KB  |  264 lines
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #include "config.h"
  5. #include "lint.h"
  6.  
  7. /*
  8.  * stralloc.c - string management.
  9.  *
  10.  * All strings are stored in an extensible hash table, with reference counts.
  11.  * free_string decreases the reference count; if it gets to zero, the string
  12.  * will be deallocated.  add_string increases the ref count if it finds a
  13.  * matching string, or allocates it if it cant.  There is no way to allocate
  14.  * a string of a particular size to fill later (hash wont work!), so you'll
  15.  * have to copy things freom a static (or malloced and later freed) buffer -
  16.  * that is, if you want to avoid space leaks...
  17.  *
  18.  * Current overhead:
  19.  *    8 bytes per string (next pointer, and 2 shorts for length and refs)
  20.  *    Strings are nearly all fairly short, so this is a significant overhead-
  21.  *    there is also the 4 byte malloc overhead and the fact that malloc
  22.  *    generally allocates blocks which are a power of 2 (should write my
  23.  *    own best-fit malloc specialised to strings); then again, GNU malloc
  24.  *    is bug free...
  25.  */
  26.  
  27. /*
  28.  * there is also generic hash table management code, but strings can be shared
  29.  * (that was the point of this code), will be unique in the table,
  30.  * require a reference count, and are malloced, copied and freed at
  31.  * will by the string manager.  Besides, I wrote this code first :-).
  32.  * Look at htable.c for the other code.  It uses the Hash() function
  33.  * defined here, and requires hashed objects to have a pointer to the
  34.  * next element in the chain (which you specify when you call the functions).
  35.  */
  36.  
  37. #define    MAXSHORT    (1 << (sizeof(short)*8 - 2))
  38. #define    WORD_ALIGN_BIT    0x3    /* these are 0 for aligned ptrs */
  39.  
  40. char * xalloc();
  41. #ifndef _AIX
  42. char * strcpy();
  43. #endif
  44.  
  45. static int num_distinct_strings = 0;
  46. int bytes_distinct_strings = 0;
  47. static int allocd_strings = 0;
  48. static int allocd_bytes = 0;
  49. int overhead_bytes = 0;
  50. static int search_len = 0;
  51. static int num_str_searches = 0;
  52.  
  53. /*
  54.  * strings are stored:
  55.  *    (char * next) (short numrefs) string
  56.  *                      ^
  57.  *                pointer points here
  58.  */
  59.  
  60. #define    NEXT(str)    (*(char **)((char *) (str) - sizeof(short)    \
  61.                            - sizeof(int)))
  62. #define    REFS(str)    (*(short *)((char *) (str) - sizeof(short)))
  63.  
  64. /*
  65.  * hash table - list of pointers to heads of string chains.
  66.  * Each string in chain has a pointer to the next string and a
  67.  * reference count (char *, int) stored just before the start of the string.
  68.  * HTABLE_SIZE is in config.h, and should be a prime, probably between
  69.  * 1000 and 5000.
  70.  */
  71.  
  72. static char ** base_table = 0;
  73.  
  74. static void init_strings()
  75. {
  76.     int x;
  77.     base_table = (char **) xalloc(sizeof(char *) * HTABLE_SIZE);
  78.     overhead_bytes += (sizeof(char *) * HTABLE_SIZE);
  79.  
  80.     for (x=0; x<HTABLE_SIZE; x++)
  81.         base_table[x] = 0;
  82. }
  83.  
  84. /*
  85.  * generic hash function.  This is probably overkill; I haven't checked the
  86.  * stats for different prime numbers, etc.
  87.  */
  88.  
  89. static int StrHash(s)
  90. char * s;
  91. {
  92.     if (!base_table)
  93.         init_strings();
  94.  
  95.     return hashstr(s, 20, HTABLE_SIZE);
  96. }
  97.  
  98. /*
  99.  * Looks for a string in the table.  If it finds it, returns a pointer to
  100.  * the start of the string part, and moves the entry for the string to
  101.  * the head of the pointer chain.  One thing (blech!) - puts the previous
  102.  * pointer on the hash chain into fs_prev.
  103.  */
  104.  
  105. char * findstring(s)
  106. char * s;
  107. {
  108.     char * curr, *prev;
  109.     int h = StrHash(s);
  110.  
  111.     curr = base_table[h];
  112.     prev = 0;
  113.     num_str_searches++;
  114.  
  115.     while (curr) {
  116.         search_len++;
  117.         if (*curr == *s && !strcmp(curr, s)) { /* found it */
  118.         if (prev) { /* not at head of list */
  119.             NEXT(prev) = NEXT(curr);
  120.             NEXT(curr) = base_table[h];
  121.             base_table[h] = curr;
  122.             }
  123.         return(curr);    /* pointer to string */
  124.         }
  125.         prev = curr;
  126.         curr = NEXT(curr);
  127.         }
  128.     
  129.     return(0); /* not found */
  130. }
  131.  
  132. /*
  133.  * Make a space for a string.  This is rather nasty, as we want to use
  134.  * alloc/free, but malloc overhead is generally severe.  Later, we
  135.  * will have to compact strings...
  136.  */
  137.  
  138. static char * alloc_new_string(string)
  139. char * string;
  140. {
  141.     char * s = xalloc(1 + strlen(string) + sizeof(char *) + sizeof(short));
  142.     int h = StrHash(string);
  143.  
  144.     s += sizeof(char *) + sizeof(short);
  145.     strcpy(s, string);
  146.     REFS(s) = 0;
  147.     NEXT(s) = base_table[h];
  148.     base_table[h] = s;
  149.     num_distinct_strings++;
  150.     bytes_distinct_strings += 4 + (strlen(s) +3) & ~3;
  151.     overhead_bytes += sizeof(char *) + sizeof(short);
  152.     return(s);
  153. }
  154.  
  155. char * make_shared_string(str)
  156. char * str;
  157. {
  158.     char * s;
  159.  
  160.     s = findstring(str);
  161.     if (!s)
  162.         s = alloc_new_string(str);
  163.     REFS(s)++;
  164.     allocd_strings++;
  165.     allocd_bytes += 4 + (strlen(str) + 3) & ~3;
  166.     return(s);
  167. }
  168.  
  169. /*
  170.  * free_string - reduce the ref count on a string.  Various sanity
  171.  * checks applied, the best of them being that a add_string allocated
  172.  * string will point to a word boundary + sizeof(int)+sizeof(short),
  173.  * since malloc always allocates on a word boundary.
  174.  * On systems where a short is 1/2 a word, this gives an easy check
  175.  * to see whather we did in fact allocate it.
  176.  *
  177.  * Don't worry about the overhead for all those checks!
  178.  */
  179.  
  180. /*
  181.  * function called on free_string detected errors; things return checked(s).
  182.  */
  183.  
  184. static void checked(s, str) char * s, *str;
  185. {
  186.     fprintf(stderr, "%s (\"%s\")\n", s, str);
  187.     fatal(s); /* brutal - debugging */
  188. }
  189.  
  190. void free_string(str)
  191. char * str;
  192. {
  193.     char * s;
  194.  
  195.     allocd_strings--;
  196.     allocd_bytes -= 4 + (strlen(str) + 3) & ~3;
  197.  
  198. #ifndef    BUG_FREE
  199. #ifdef    dcheck    /* GNU malloc range check flag */
  200.     { int align;
  201.     align = (((int)str) - sizeof(int) - sizeof(short)) & WORD_B_MASK;
  202.     if (align)
  203.         checked("Free string: improperly aligned string!", str);
  204.     }
  205. #endif /* dcheck */
  206. #endif
  207.  
  208.     s = findstring(str); /* moves it to head of table if found */
  209. #ifndef    BUG_FREE
  210.     if (!s) {
  211.         checked("Free string: not found in string table!", str);
  212.         return;
  213.     }
  214.     if (s != str) {
  215.         checked("Free string: string didnt hash to the same spot!", str);
  216.         return;
  217.     }
  218.  
  219.     if (REFS(s) <= 0) {
  220.         checked("Free String: String refs zero or -ve!", str);
  221.         return;
  222.     }
  223. #endif    /* BUG_FREE */
  224.  
  225.     if (REFS(s) > MAXSHORT) return;
  226.     REFS(s)--;
  227.     if (REFS(s) > 0) return;
  228.  
  229.     /* It will be at the head of the hash chain */
  230.     base_table[StrHash(str)] = NEXT(s);
  231.     num_distinct_strings--;
  232.     /* We know how much overhead malloc has */
  233.     bytes_distinct_strings-= 4 + (strlen(s) + 3) & ~3;
  234.     overhead_bytes -= sizeof(short) + sizeof(char *);
  235.     free(s-sizeof(short)-sizeof(char *));
  236.  
  237.     return;
  238. }
  239.  
  240. /*
  241.  * you think this looks bad!  and we didn't even tell them about the
  242.  * GNU malloc overhead!  tee hee!
  243.  */
  244.  
  245. int add_string_status(verbose)
  246.     int verbose;
  247. {
  248.     if (verbose) {
  249.     add_message("\nShared string hash table:\n");
  250.     add_message("-------------------------\t Strings    Bytes\n");
  251.     }
  252.     add_message("Strings malloced\t\t%8d %8d + %d overhead\n",
  253.         num_distinct_strings, bytes_distinct_strings, overhead_bytes);
  254.     if (verbose) {
  255.     add_message("Total asked for\t\t\t%8d %8d\n",
  256.             allocd_strings, allocd_bytes);
  257.     add_message("Space actually required/total string bytes %d%%\n",
  258.             (bytes_distinct_strings + overhead_bytes)*100 / allocd_bytes);
  259.     add_message("Searches: %d    Average search length: %6.3f\n",
  260.             num_str_searches, (double)search_len / num_str_searches);
  261.     }
  262.     return(bytes_distinct_strings + overhead_bytes);
  263. }
  264.